package dataStructure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;

public class BiTree {
    private Character data;
    public BiTree lchild;
    public BiTree rchild;
    Boolean ltag,rtag;


    public BiTree() {
        this.data = null;
        this.lchild = null;
        this.rchild = null;
        this.rtag = false;
        this.ltag = false;
    }

    public Boolean isNotEmpty() {
        return data != null;
    }

    public ArrayList<Character> create(BiTree T, ArrayList<Character> list) {
        if (list.size() == 0) {
            return list;
        }
        if (list.get(0) == '#') {
            list.remove(0);
            T = null;
            return list;
        }
        T.setData(list.get(0));
        list.remove(0);
        T.lchild = new BiTree();
        ArrayList<Character> arrayList = T.lchild.create(T.lchild, list);
        T.rchild = new BiTree();
        ArrayList<Character> arrayList1 = T.rchild.create(T.rchild, arrayList);
        return arrayList1;
    }

    /**
     * 前序遍历
     *
     * @return 子节点数值
     */
    public void PreOrder() {
        System.out.println(getData());
        if (lchild.isNotEmpty()) {
            lchild.PreOrder();
        }
        if (rchild.isNotEmpty()) {
            rchild.PreOrder();
        }
    }

    public void PreOrder2(BiTree T) {
        stack<BiTree> stack = new stack<>();
        BiTree p = T;
        while (!stack.StackEmpty() || p.isNotEmpty()) {
            if (p.isNotEmpty()) {
                System.out.println(p.getData());
                stack.Push(p);
                p = p.lchild;
            } else {
                p = stack.Pop();

                p = p.rchild;
            }
        }
    }

    /**
     * 中序遍历
     */
    public void InOrder() {
        if (lchild.getData() != null) {
            lchild.InOrder();
        }
        System.out.println(getData());
        if (rchild.getData() != null) {
            rchild.InOrder();
        }
    }

    public void InOrder2(BiTree T) {
        stack<BiTree> stack = new stack<>();
        BiTree p = T;
        while (!stack.StackEmpty() || p.isNotEmpty()) {
            if (p.isNotEmpty()) {

                stack.Push(p);
                p = p.lchild;
            } else {
                p = stack.Pop();
                System.out.println(p.getData());
                p = p.rchild;
            }
        }


    }


    /**
     * 后序遍历
     */
    public void PostOrder() {
        if (lchild.getData() != null) {
            lchild.PostOrder();
        }
        if (rchild.getData() != null) {
            rchild.PostOrder();
        }
        System.out.println(getData());
    }

    public void PostOrder2(BiTree T) {
        stack<BiTree> stack = new stack<>();
        BiTree p = T;
        BiTree r = new BiTree();
        while (!stack.StackEmpty() || p.isNotEmpty()) {
            if (p.isNotEmpty()) {
                stack.Push(p);
                p = p.lchild;
            } else {
                p = stack.GetPop();
                if (!p.rchild.isNotEmpty() || p.rchild==r) {
                    System.out.println(p.getData());
                    p = stack.Pop();
                    r = p;
                    p.data =null;
                    continue;
                }
                p = p.rchild;
            }
        }
    }
static class Tread{

    public static BiTree pre = new BiTree();
    /**
     * 中序线索化
     * @param p
     */
    public static void InTread(BiTree p){
        if (p.isNotEmpty()){
            InTread(p.lchild);
            if (!p.lchild.isNotEmpty()){
                p.ltag = true;
                p.lchild = pre;
            }
            if (pre.isNotEmpty()&&!pre.rchild.isNotEmpty()){
                pre.rchild = p;
                pre.rtag = true;
            }
            pre = p;
            InTread(p.rchild);
        }
    }
    public static void doInTread(BiTree p){
        if (p.isNotEmpty()){
            InTread(p);
            pre.rchild = new BiTree();
            pre.rtag = true;
        }
    }
}





    /**
     * 中序线索遍历
     * @param p
     */
    public BiTree Firstnode(BiTree p){
        while (!p.ltag){
            p=p.lchild;
        }
        return p;
    }
    public BiTree Nextnode(BiTree p){
        if (p.rtag){
            return p.rchild;
        }else {
            return Firstnode(p.rchild);
        }
    }
    public void InTreadOrder(BiTree T){
        for(BiTree p = Firstnode(T);p.isNotEmpty();p=Nextnode(p)){
            System.out.println(p.getData());
//            System.out.println("zuo   ");
//            System.out.println(p.lchild.getData());
//            System.out.println("you");
//            System.out.println(p.rchild.getData());
        }
    }



    public Character getData() {
        return data;
    }

    public void setData(Character data) {
        this.data = data;
    }

    public static void main(String[] args) {
        ArrayList<Character> list = new ArrayList<Character>(){{
            add('1');
            add('2');
            add('#');
            add('4');
            add('6');
            add('#');
            add('#');
            add('#');
            add('3');
            add('#');
            add('5');
            add('#');
            add('#');
        }};
        BiTree tree = new BiTree();
        tree.create(tree,list);
        BiTree.Tread.doInTread(tree);
        System.out.println("-------------------------------------");
        tree.InTreadOrder(tree);
    }
}
